package 中等.栈;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 根据 逆波兰表示法，求该后缀表达式的计算结果。
 * 有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
 * 说明：
 * 整数除法只保留整数部分。
 * 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/8Zf90G
 */
public class 后缀表达式_offer036 {

    public static void main(String[] args) {

        String[] tokens = {"2", "1", "+", "3", "*"};
        System.out.println(new 后缀表达式_offer036().evalRPN(tokens));

    }

    /**
     * 遇到数字时入栈，遇到操作符时，弹出栈顶两个元素，将用操作符计算之后结果入栈
     *
     * @param tokens
     * @return
     */
    public int evalRPN(String[] tokens) {
        Deque<Integer> stack = new ArrayDeque<>();
        for (String token : tokens) {
            if (isOperate(token)) {
                Integer afterNum = stack.pollFirst();
                Integer beforeNum = stack.pollFirst();
                stack.addFirst(compute(beforeNum, afterNum, token));
            } else {
                stack.addFirst(Integer.valueOf(token));
            }
        }
        return stack.peek();
    }

    private boolean isOperate(String str) {
        return str.equals("+") || str.equals("-")
                || str.equals("*") || str.equals("/");
    }

    private int compute(int beforeNum, int afterNum, String operate) {
        switch (operate) {
            case "+":
                return beforeNum + afterNum;
            case "-":
                return beforeNum - afterNum;
            case "*":
                return beforeNum * afterNum;
            default:
                return beforeNum / afterNum;
        }
    }

}
